﻿namespace AdvancedTraining.Lesson49;

/// <summary>
/// LeetCode 446. 算术切片 II - 子序列
/// 给定一个整数数组 A，返回 A 中所有算术切片的数目。
/// 算术切片是指至少包含三个元素的子序列，且相邻元素之间的差值相等。
/// </summary>
/// <remarks>
/// 算法思路：
/// 1. 动态规划 + 哈希表优化
/// 2. 对于每个位置i，记录以i结尾的等差子序列信息
/// 3. maps[i][diff] 表示以i结尾，公差为diff的等差子序列数量
/// 4. 对于每个j < i，计算diff = A[i] - A[j]，然后：
///    - maps[j][diff]是以j结尾的等差子序列数量
///    - 这些子序列加上A[i]后形成新的等差子序列
///    - ans += maps[j][diff] 统计所有长度≥3的等差子序列
///    - maps[i][diff] += maps[j][diff] + 1 (加上新的长度为2的序列)
///
/// 时间复杂度：O(N^2)
/// 空间复杂度：O(N^2)
/// </remarks>
public class ArithmeticSlicesIiSubsequence //leetcode_0446
{
    /// <summary>
    /// 计算数组中等差子序列的数量
    /// </summary>
    /// <param name="arr">输入数组</param>
    /// <returns>等差子序列的数量</returns>
    public static int NumberOfArithmeticSlices(int[] arr)
    {
        var n = arr.Length;
        var ans = 0;
        var maps = new List<Dictionary<int, int>>();
        for (var i = 0; i < n; i++)
        {
            maps.Add(new Dictionary<int, int>());
            //  ....j...i（结尾）
            for (var j = i - 1; j >= 0; j--)
            {
                var diff = arr[i] - (long)arr[j];
                if (diff is <= int.MinValue or > int.MaxValue) continue;
                var dif = (int)diff;
                var count = maps[j].GetValueOrDefault(dif, 0);
                ans += count;
                maps[i][dif] = maps[i].GetValueOrDefault(dif, 0) + count + 1;
            }
        }

        return ans;
    }

    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== 等差子序列测试 ===");

        // 测试用例1：全相同的数组
        var test1 = new[] { 7, 7, 7, 7, 7 };
        var result1 = NumberOfArithmeticSlices(test1);
        Console.WriteLine($"测试用例1: [{string.Join(", ", test1)}]");
        Console.WriteLine($"结果: {result1}, 期望: 16");
        Console.WriteLine(result1 == 16 ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例2：LeetCode官方示例
        var test2 = new[] { 2, 4, 6, 8, 10 };
        var result2 = NumberOfArithmeticSlices(test2);
        Console.WriteLine($"测试用例2: [{string.Join(", ", test2)}]");
        Console.WriteLine($"结果: {result2}, 期望: 7");
        Console.WriteLine(result2 == 7 ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例3：包含负数
        var test3 = new[] { 1, 3, 5, 7, 9, 11, 13 };
        var result3 = NumberOfArithmeticSlices(test3);
        Console.WriteLine($"测试用例3: [{string.Join(", ", test3)}]");
        Console.WriteLine($"结果: {result3}, 期望: 20");
        Console.WriteLine(result3 == 20 ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例4：单个元素
        var test4 = new[] { 5 };
        var result4 = NumberOfArithmeticSlices(test4);
        Console.WriteLine($"测试用例4: [{string.Join(", ", test4)}]");
        Console.WriteLine($"结果: {result4}, 期望: 0");
        Console.WriteLine(result4 == 0 ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例5：两个元素
        var test5 = new[] { 1, 2 };
        var result5 = NumberOfArithmeticSlices(test5);
        Console.WriteLine($"测试用例5: [{string.Join(", ", test5)}]");
        Console.WriteLine($"结果: {result5}, 期望: 0");
        Console.WriteLine(result5 == 0 ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例6：三个元素形成等差数列
        var test6 = new[] { 1, 2, 3 };
        var result6 = NumberOfArithmeticSlices(test6);
        Console.WriteLine($"测试用例6: [{string.Join(", ", test6)}]");
        Console.WriteLine($"结果: {result6}, 期望: 1");
        Console.WriteLine(result6 == 1 ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例7：复杂情况
        var test7 = new[] { 7, 7, 7, 7 };
        var result7 = NumberOfArithmeticSlices(test7);
        Console.WriteLine($"测试用例7: [{string.Join(", ", test7)}]");
        Console.WriteLine($"结果: {result7}, 期望: 5");
        Console.WriteLine(result7 == 5 ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例8：无等差子序列
        var test8 = new[] { 1, 2, 4, 8, 16 };
        var result8 = NumberOfArithmeticSlices(test8);
        Console.WriteLine($"测试用例8: [{string.Join(", ", test8)}]");
        Console.WriteLine($"结果: {result8}, 期望: 0");
        Console.WriteLine(result8 == 0 ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例9：混合情况
        var test9 = new[] { 1, 3, 5, 8, 11, 14 };
        var result9 = NumberOfArithmeticSlices(test9);
        Console.WriteLine($"测试用例9: [{string.Join(", ", test9)}]");
        Console.WriteLine($"结果: {result9}, 期望: 4");
        Console.WriteLine(result9 == 4 ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例10：空数组
        var test10 = Array.Empty<int>();
        var result10 = NumberOfArithmeticSlices(test10);
        Console.WriteLine($"测试用例10: []");
        Console.WriteLine($"结果: {result10}, 期望: 0");
        Console.WriteLine(result10 == 0 ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        Console.WriteLine("=== 算法说明 ===");
        Console.WriteLine("等差子序列：至少包含3个元素的子序列，相邻元素差值相等");
        Console.WriteLine("动态规划思想：maps[i][diff]记录以i结尾，公差为diff的等差子序列数量");
        Console.WriteLine("时间复杂度：O(N^2)，空间复杂度：O(N^2)");
    }
}